//假设是4行，那么s的每一个字符的行数：1234321234321.....
class Solution {
public:
    string convert(string s, int numRows) {
        vector<string> ret(numRows, string());

        int rows = 1;
        bool flag = true;
        for (int i = 0; i < s.size(); ++i)
        {
            ret[rows - 1] += s[i];
            if (flag)
            {
                ++rows;
                if (rows >= numRows)
                {
                    rows = numRows;
                    flag = false;
                }
            }
            else
            {
                --rows;
                if (rows <= 1)
                {
                    rows = 1;
                    flag = true;
                }
            }
        }

        string temp;
        for (auto str : ret)
            temp += str;

        return temp;
    }
};

class Solution {
private:
    //返回带有n个空格的字符串
    string blank(int n)
    {
        return string(n, ' ');
    }

    //以分隔符 sep 组合 words 中 [left, right)的字符串
    string join(vector<string>& words, int left, int right, string sep)
    {
        string ret = words[left];
        for (int i = left + 1; i < right; ++i)
            ret += sep + words[i];

        return ret;
    }

public:
    vector<string> fullJustify(vector<string>& words, int maxWidth) {
        vector<string> ret;
        int n = words.size();

        int right = 0;
        while (true)
        {
            int left = right;
            int max_len = 0;

            //right - left 为：每个单词中间至少一个空格
            while (right < n && max_len + words[right].size() + right - left <= maxWidth)
            {
                max_len += words[right].size();
                ++right;
            }

            //最后一行
            if (right == n)
            {
                string s = join(words, left, right, " ");

                ret.emplace_back(s + blank(maxWidth - s.size()));
                break;
            }

            int num_words = right - left;
            int num_spaces = maxWidth - max_len;

            //如果该行只有一个单词
            if (num_words == 1)
            {
                ret.emplace_back(words[left] + blank(num_spaces));
            }
            else    //如果该行有多个单词
            {
                int avg_spaces = num_spaces / (num_words - 1);      //每个单词中间至少有的空格数
                int extra_spaces = num_spaces % (num_words - 1);    //多出的空格数

                //对于前extra_spaces个单词，其之间的空格个数要比avg_spaces多一个
                string s1 = join(words, left, left + extra_spaces + 1, blank(avg_spaces + 1));

                string s2 = join(words, left + extra_spaces + 1, right, blank(avg_spaces));

                //blank(avg_spaces)为s1和s2之间的空格
                ret.emplace_back(s1 + blank(avg_spaces) + s2);
            }
        }
       
       return ret;
    }
};